/**
 * //给定一个整数数组
 * // prices，其中第 prices[i] 表示第 i 天的股票价格 。
 * //
 * // 设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
 * //
 * //
 * // 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
 * //
 * //
 * // 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
 * //
 * //
 * //
 * // 示例 1:
 * //
 * //
 * //输入: prices = [1,2,3,0,2]
 * //输出: 3
 * //解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]
 * //
 * // 示例 2:
 * //
 * //
 * //输入: prices = [1]
 * //输出: 0
 * //
 * //
 * //
 * //
 * // 提示：
 * //
 * //
 * // 1 <= prices.length <= 5000
 * // 0 <= prices[i] <= 1000
 * //
 * //
 * // Related Topics 数组 动态规划 👍 1295 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

public class ID00309BestTimeToBuyAndSellStockWithCooldown {
    public static void main(String[] args) {
        Solution solution = new ID00309BestTimeToBuyAndSellStockWithCooldown().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxProfit(int[] prices) {


            int n = prices.length;

            if (n == 1) return 0;

            //一个数组来存放每天两种状态下的最大利润
            int[][] dp = new int[n][2];

            //初始化
            //第一天不持有
            dp[0][0] = 0;
            //第一天持有
            dp[0][1] = -prices[0];

            //第二天不持有，可以从第一天不持有dp[0][0] 和 第一天持有第二天卖得出dp[0][1] + prices[1]
            dp[1][0] = Math.max(dp[0][0], dp[0][1] + prices[1]);
            //第二天持有，可以从第一天持有dp[0][1] 和 第一天不持有第二天持有得出dp[0][0] - prices[1]
            dp[1][1] = Math.max(dp[0][1], dp[0][0] - prices[1]);


            //dp
            for (int i = 2; i < n; i++) {
                //第三天开始，
                //不持有
                //可以从 昨天也没有 dp[i-1][0] 和 昨天有今天卖得出
                dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);

                //持有
                //可以从昨天也持有 dp[i-1][1] 和 前天（1天冷冻期）没有今天买得出----昨天没有今天不一定能不能买，所以只能从前天卖掉的情况得出
                dp[i][1] = Math.max(dp[i - 1][1], dp[i - 2][0] - prices[i]);


            }


            return Math.max(dp[n - 1][0], dp[n - 1][1]);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}